package Other;

import java.util.*;

public class leet_146 {
    public static void main(String[] args) {
        LRUCache_146 p = new LRUCache_146(2);
        p.put(1, 1);
        p.put(2,2);
        int value = p.get(1);



    }
}



class LRUCache_146 {
    // 结点类
    class DLinkNode{
        // 键
        int key;
        // 值
        int value;
        // 前面结点
        DLinkNode pre;
        // 后序结点
        DLinkNode next;

        public DLinkNode() {
        }

        public DLinkNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }


    // 最大容量
    int capacity;
    // 记录其信息的
    Map<Integer, DLinkNode> valueMap = new HashMap<>();
    // 已经使用的情况
    int used;
    // 首尾结点
    DLinkNode head;
    DLinkNode tail;

    // 定义LRU算法类
    public LRUCache_146(int capacity) {
        this.capacity = capacity;
        this.used = 0;
        // 首节点使用最小值
        head = new DLinkNode(-1, 0);
        // 尾结点使用最大值
        tail = new DLinkNode(10001, 0);
        head.next = tail;
        tail.pre = head;
    }

    // 定义放入函数
    public void put(int key, int value) {
        // 如何放入的键存在
        if(valueMap.containsKey(key)){
            DLinkNode Node = valueMap.get(key);
            // 修改value
            Node.value = value;
            // 转移位置
            addNode(key, Node);
        }else {
            // 这个结点不存在
            DLinkNode Node = new DLinkNode(key, value);
            // 判断使用情况来进行增加行为
            if(used==capacity){
                // 队列已经存储满
                deleteNode();
                addNode(key, Node);
            }else {
                // 还没有存储满
                addNode(key, Node);
            }
        }
    }


    /**
     * 取出 key 对应 value
     * @param key 带取值的key
     * @return  带取值的value
     */
    public int get(int key) {
        if(valueMap.containsKey(key)){
            DLinkNode Node = valueMap.get(key);
            int value = Node.value;
            // 把刚刚取出的结点放入首节点
            addNode(key, Node);
            return value;
        }else {
            return -1;
        }
    }

    /**
     * 尾结点变化
     */
    public void deleteNode(){
        // 找到最后的一个节点 与 key
        DLinkNode Node = tail.pre;
        int key = Node.key;
        // 跳过原来最初的节点
        DLinkNode preNode = Node.pre;
        preNode.next=tail;
        tail.pre=preNode;
        // 在hash映射表中删除该字段
        this.valueMap.remove(key);
        this.used--;
    }


    /**
     * 首节点变化
     * @param key    key值
     * @param Node   需要移动到首节点的结点
     */
    public void addNode(int key, DLinkNode Node){
        // 如果不存在于结点内，需要增加使用数量
        if(!valueMap.containsKey(key)){
            // 找到第一个节点
            DLinkNode firstNode = head.next;
            head.next = Node;
            Node.pre = head;
            firstNode.pre = Node;
            Node.next = firstNode;
            // 放入hash中
            this.valueMap.put(key, Node);
            this.used++;
        }else {
            // 如果该元素本来就存在首先将该元素的前后直接关联
            DLinkNode afterNode = Node.pre;
            DLinkNode laterNode = Node.next;
            afterNode.next = laterNode;
            laterNode.pre = afterNode;
            // 在考虑首位元素的移动问题
            // 找到第一个节点
            DLinkNode firstNode = head.next;
            head.next = Node;
            Node.pre = head;
            firstNode.pre = Node;
            Node.next = firstNode;
        }
    }
}




